/*
 * @lc app=leetcode.cn id=215 lang=cpp
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start
class Solution
{
public:
  int ans;

  int findKthLargest(vector<int>& nums, int k)
  {
    TOPK(nums, 0, nums.size() - 1, k);
    return ans;
  }

  void TOPK(vector<int>& nums, int low, int high, int k)
  {
    if (low > high)
      return;
    int mid = Partition(nums, low, high);
    if (mid == k - 1)
      ans = nums[mid];
    else if (mid < k - 1)
      TOPK(nums, mid + 1, high, k);
    else
      TOPK(nums, low, mid - 1, k);
  }

  int Partition(vector<int>& nums, int low, int high)
  {
    int tmp = nums[low];
    while (low < high) {
      while (low < high && nums[high] <= tmp)
        --high;
      nums[low] = nums[high];
      while (low < high && nums[low] >= tmp)
        ++low;
      nums[high] = nums[low];
    }
    nums[low] = tmp;
    return low;
  }
};
// @lc code=end
